package Medium;

public class LC0328 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode oddEvenList(ListNode head) {
        ListNode oddHead = head;
        if (oddHead == null) return head;
        ListNode evenHead = head.next;
        if (evenHead == null) return head;

        ListNode oddPtr = oddHead, evenPtr = evenHead;
        while (true) {
            oddPtr.next = evenPtr.next;
            if (evenPtr.next != null) {
                oddPtr = evenPtr.next;
            }
            else { // evenPtr指向链表末尾
                break; // 收尾工作放在while外
            }

            // 此时oddPtr在evenPtr后面，需要移动evenPtr
            evenPtr.next = oddPtr.next;
            if (oddPtr.next != null) {
                evenPtr = oddPtr.next;
            }
            else {
                break;
            }
        }

        oddPtr.next = evenHead;
        return head;
    }
}
